home *** CD-ROM | disk | FTP | other *** search
/ ADA Programming Guide / ADA Programming Guide.iso / ada_gnu / adainc / s-expmod.adb < prev    next >
Text File  |  1996-01-30  |  3KB  |  79 lines
  1. ------------------------------------------------------------------------------
  2. --                                                                          --
  3. --                         GNAT RUNTIME COMPONENTS                          --
  4. --                                                                          --
  5. --                       S Y S T E M . E X P _ M O D                        --
  6. --                                                                          --
  7. --                                 B o d y                                  --
  8. --                                                                          --
  9. --                            $Revision: 1.5 $                              --
  10. --                                                                          --
  11. --           Copyright (c) 1992,1993,1994 NYU, All Rights Reserved          --
  12. --                                                                          --
  13. -- The GNAT library is free software; you can redistribute it and/or modify --
  14. -- it under terms of the GNU Library General Public License as published by --
  15. -- the Free Software  Foundation; either version 2, or (at your option) any --
  16. -- later version.  The GNAT library is distributed in the hope that it will --
  17. -- be useful, but WITHOUT ANY WARRANTY;  without even  the implied warranty --
  18. -- of MERCHANTABILITY  or  FITNESS FOR  A PARTICULAR PURPOSE.  See the  GNU --
  19. -- Library  General  Public  License for  more  details.  You  should  have --
  20. -- received  a copy of the GNU  Library  General Public License  along with --
  21. -- the GNAT library;  see the file  COPYING.LIB.  If not, write to the Free --
  22. -- Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.        --
  23. --                                                                          --
  24. ------------------------------------------------------------------------------
  25.  
  26. package body System.Exp_Mod is
  27.  
  28.    -----------------
  29.    -- Exp_Modular --
  30.    -----------------
  31.  
  32.    function Exp_Modular
  33.      (Left    : Integer;
  34.       Modulus : Integer;
  35.       Right   : Natural)
  36.       return    Integer
  37.    is
  38.       Result : Integer := 1;
  39.       Factor : Integer := Left;
  40.       Exp    : Natural := Right;
  41.  
  42.       function Mult (X, Y : Integer) return Integer;
  43.       pragma Inline (Mult);
  44.       --  Modular multiplication. Note that we can't take advantage of the
  45.       --  compiler's circuit, because the modulus is not known statically.
  46.  
  47.       function Mult (X, Y : Integer) return Integer is
  48.       begin
  49.          return Integer
  50.            (Long_Long_Integer (X) * Long_Long_Integer (Y)
  51.              mod Long_Long_Integer (Modulus));
  52.       end Mult;
  53.  
  54.    --  Start of processing for Exp_Modular
  55.  
  56.    begin
  57.       --  We use the standard logarithmic approach, Exp gets shifted right
  58.       --  testing successive low order bits and Factor is the value of the
  59.       --  base raised to the next power of 2.
  60.  
  61.       --  Note: it is not worth special casing the cases of base values -1,0,+1
  62.       --  since the expander does this when the base is a literal, and other
  63.       --  cases will be extremely rare.
  64.  
  65.       while Exp /= 0 loop
  66.          if Exp rem 2 /= 0 then
  67.             Result := Mult (Result, Factor);
  68.          end if;
  69.  
  70.          Factor := Mult (Factor, Factor);
  71.          Exp := Exp / 2;
  72.       end loop;
  73.  
  74.       return Result;
  75.  
  76.    end Exp_Modular;
  77.  
  78. end System.Exp_Mod;
  79.